package com.cat.gridChart;

/**
 *   @description https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
 *   @author 曲大人的喵
 *   @create 2025/9/7 19:09
 *   @since JDK17
 */

public class Solution12 {
    static int[][] q = new int[10010][2];
    static int[][] d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    boolean[][] vis;
    public int nearestExit(char[][] maze, int[] entrance) {
        int n = maze.length, m = maze[0].length, ans = 0, t = 0, h = 0;
        q[t++] = new int[]{entrance[0], entrance[1]};
        vis = new boolean[n][m];
        vis[q[0][0]][q[0][1]] = true;
        while (h < t) { //
            ans++;
            for (int end = t; h < end; h++) {   // 一层一层弹出
                int[] pos = q[h];
                for (int i = 0; i < 4; i++) {
                    int nx = d[i][0] + pos[0], ny = d[i][1] + pos[1];
                    if (nx == -1 || nx == n || ny == -1 || ny == m || vis[nx][ny] || maze[nx][ny] == '+') {    // 之前的已经用过了
                        continue;
                    }
                    if (nx == 0 || nx == n - 1 || ny == 0 || ny == m - 1) {
                        return ans;
                    }
                    q[t++] = new int[]{nx, ny}; // 加入队列中
                    vis[nx][ny] = true;
                }
            }
        }
        return -1;
    }
}
